package week06

// 213. 打家劫舍 II
// https://leetcode-cn.com/problems/house-robber-ii/

func rob(nums []int) int {
	if len(nums) == 1 {
		return nums[0]
	}

	var dp = make([][]int, len(nums)+1)
	for i := range dp {
		dp[i] = make([]int, 2)
	}
	// 第一家不偷，最后一家可偷可不偷
	// j: 0-不偷  1-偷
	for i := 2; i <= len(nums); i++ {
		for j := 0; j <= 1; j++ {
			dp[i][j] = max(dp[i][j], dp[i-1][j])
			if i == 1 {
				continue
			}
			if j == 0 {
				dp[i][0] = max(dp[i][0], dp[i-1][1])
			} else {
				dp[i][1] = max(dp[i][1], dp[i-1][0] + nums[i-1])
			}
		}
	}
	var ans = max(dp[len(nums)][0], dp[len(nums)][1])

	// 第一家偷，最后一家不可偷
	for i := range dp {
		dp[i] = make([]int, 2)
	}
	for i := 1; i <= len(nums); i++ {
		for j := 0; j <= 1; j++ {
			dp[i][j] = max(dp[i][j], dp[i-1][j])
			if i == len(nums) {
				continue
			}
			if j == 0 {
				dp[i][0] = max(dp[i][0], dp[i-1][1])
			} else {
				dp[i][1] = max(dp[i][1], dp[i-1][0] + nums[i-1])
			}
		}
	}
	ans = max(ans, dp[len(nums)][0])
	ans = max(ans, dp[len(nums)][1])
	return ans
}

func max(x, y int) int {
	if x > y {
		return x
	}
	return y
}